package com.cqs.leetcode.backtrack;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lixiaowen
 * @create 2019-12-16
 */
public class NQueens52 {


    /**
     * 列放置情况
     */
    private int[] col;
    /**
     * "/"对角线情况
     * 特点：每条“/”对角线相加均是同一常数，不同的对角线之和不同
     * 一共有2×n-1条
     */
    private int[] cross;
    /**
     * 每条“/”对角线坐标相是同一常数，不同的对角线之差不同
     * 因为存在负数，为了方便处理使用set存储
     */
    private Set<Integer> cross2 = new HashSet<>();
    /**
     * 方案数量
     */
    private int result = 0;

    public int totalNQueens(int n) {
        col = new int[n];
        cross = new int[2 * n - 1];
        totalNQueens(n, 0);
        return result;
    }


    public void totalNQueens(final int n, int level){
        if (level == n){
            ++result;
            return;
        }
        //第level行，挨列放值
        for (int i = 0; i < n; i++) {
            //处理列
            if (col[i] == 1) continue;
            // "/"对角线检测
            if (cross[level + i] == 1) continue;
            // "\"对角线
            if (cross2.contains(level - i)) continue;
            col[i] = 1;
            cross[level + i] = 1;
            cross2.add(level - i);
            totalNQueens(n, level + 1);
            //撤销状态
            col[i] = 0;
            cross[level + i] = 0;
            cross2.remove(level - i);
        }
    }

    public static void main(String[] args) {
        NQueens52 queens = new NQueens52();
        int result = queens.totalNQueens(8);
        System.out.println("result:" + result);
    }
}
